package advance.day06;

import com.sun.deploy.panel.ITreeNode;
import jdk.internal.org.objectweb.asm.tree.FieldNode;

import javax.swing.plaf.synth.SynthSpinnerUI;
import java.util.Random;

/**
 * 描述：
 *     跳表结构
 * @author hl
 * @version 1.0
 * @date 2020/11/12 21:11
 */
public class SkipList {
    public static class Node{
        int value;
        Node up, down, left, right;

        public Node(int value) {
            this.value = value;
        }
    }
    //晋升的概率
    private static final double PROMOTE_RATE = 0.5;
    //头尾节点
    Node head, tail;
    private int maxLevel;

    public SkipList() {
        //初始化头尾节点
        head = new Node(Integer.MIN_VALUE);
        tail = new Node(Integer.MAX_VALUE);
        head.right = tail;
        tail.left = head;
    }
    //根据value找到节点
    public Node search(int value){
        Node preNode = findNode(value);
        if (preNode.value == value) {
            return preNode;
        }
        return null;
    }

    public void insert(int value){
        Node preNode = findNode(value);
        //已经存在了，无需重复插入
        if (preNode.value == value) {
            return ;
        }
        Node curNewNode = new Node(value);
        appendNode(preNode,curNewNode);
        int curLevel = 0;
        Random random = new Random();
        //随机晋升层数
        while(random.nextDouble() > PROMOTE_RATE){
            if (curLevel == maxLevel) {
                addLevel();
            }
            while(preNode.up == null){
                preNode = preNode.left;
            }
            preNode = preNode.up;
            //在上一层的合适的位置插入晋升的结点
            Node newNode = new Node(value);
            appendNode(preNode, newNode);
            newNode.down = curNewNode;
            curNewNode.up = newNode;
            curNewNode = newNode;
            curLevel++;
        }
    }

    private void addLevel() {
        maxLevel++;
        Node newHead = new Node(Integer.MIN_VALUE);
        Node newTail = new Node(Integer.MAX_VALUE);
        newHead.right = newTail;
        newTail.left = newHead;
        head.up = newHead;
        newHead.down = head;
        tail.up = newTail;
        newTail.down = tail;
        head = head.up;
        tail = tail.up;
    }

    public boolean remove(int value){
        Node removeNode = search(value);
        if(removeNode == null){
            return false;
        }
        int curLevel = 0;
        while(removeNode != null){
            deleteNode(removeNode);
            if (curLevel != 0 && removeNode.left.value == Integer.MIN_VALUE
                    && removeNode.right.value == Integer.MAX_VALUE) {
                decreseLevel(removeNode.left);
            }else{
                curLevel++;
            }
            removeNode = removeNode.up;
        }
        return true;
    }

    private void decreseLevel(Node removeHead) {
        Node removeTail = removeHead.right;
        if (removeHead.up == null) {
            removeHead.down.up = null;
            removeTail.up = null;
        }else {
            removeHead.up.down = removeHead.down;
            removeHead.down.up = removeHead.up;
            removeTail.up.down = removeHead.down;
            removeHead.down.up = removeHead.up;
        }
        maxLevel--;
    }

    private void deleteNode(Node deleteNode) {
        deleteNode.left.right = deleteNode.right;
        deleteNode.right.left = deleteNode.left;
    }


    private void appendNode(Node preNode, Node newNode) {
        newNode.right = preNode.right;
        newNode.left = preNode;
        preNode.right.left = newNode;
        preNode.right = newNode;
    }


    private Node findNode(int value) {
        Node cur = head;
        //先往右走走到不能再走，然后往下走，每一层都如此，知道走到最后一层
        while(true) {
            while (cur.right.value < Integer.MAX_VALUE && cur.right.value <= value) {
                cur = cur.right;
            }
            if (cur.down == null) {
                break;
            }
            cur = cur.down;
        }
        return cur;
    }

    public void printList(){
        Node node = findNode(Integer.MIN_VALUE);
        while(node.right.value != Integer.MAX_VALUE){
            System.out.print(node.right.value + " ");
            node = node.right;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        SkipList list=new SkipList();
        list.insert(50);
        list.insert(15);
        list.insert(13);
        list.insert(20);
        list.insert(100);
        list.insert(75);
        list.insert(99);
        list.insert(76);
        list.insert(83);
        list.insert(65);
        list.printList();
        System.out.println(list.search(50).value);
        System.out.println(list.remove(50));
        System.out.println(list.search(50));
    }
}
